package leetcode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0474.java
 * @Author : WangRuoyu
 * @Date 2023/11/6 21:45
 */


public class Q0474 {
    public int findMaxForm(String[] strs, int m, int n) {
        final int L = 100;
        int[][] f = new int[L + 1][L + 1];
        for (String str : strs) {
            int x = 0;
            int y = 0;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '0') {
                    x++;
                } else {
                    y++;
                }
            }
            for (int j = L; j >= x; j--) {
                for (int k = L; k >= y; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - x][k - y] + 1);
                }
            }
        }
        return f[m][n];
    }

    public static void main(String[] args) {
        Q0474 sl = new Q0474();
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5;
        int n = 3;
        System.out.println(sl.findMaxForm(strs, m, n));
    }
}